package uk.org.landeg.euler.problems;

import uk.org.landeg.euler.problems.framework.AbstractProblem;
import uk.org.landeg.euler.problems.framework.ProblemLauncher;

public class Problem085 extends AbstractProblem {

	public static void main(String[] args) {
		ProblemLauncher launcher = new ProblemLauncher(new Problem085());
		launcher.solve();
	}

	@Override
	public String getDescription() {
		return "Investigating the number of rectangles in a rectangular grid.";
	}

	@Override
	public Integer getProblemNumber() {
		return 85;
	}

	@Override
	public Object solve() {
		notes.add("Number of rectangles of each side is given by the matrix;");
		notes.add("1  2  3  4  5");
		notes.add("2  4  6  8  10");
		notes.add("3  6  9  12 15");
		notes.add("4  8  12 16 20");
		notes.add("5  10 15 20 25");
		notes.add("The sum of the contained values is the number of sub-rectangles in the rectangle in question");
		notes.add("The sum along one edge is 1+2+3+...+x = (1 + x) * x/2");
		notes.add("The sum of contained values is x*y*(1+x)(1+y)/4 ");
		
		long eval;
		int x,y,mx = 0,my = 0;
		long target = (long)(2e6)*4, mDiff = (long)8e6, diff;
		notes.add("Setting target to " + target);
		
		xloop : for (x = 1 ; x < 2000 ; x++) {
			for (y = 1; y < 2000 ; y++) {
				eval = x * y * (1+x) * (1+y);
				if (eval > target) {
					continue xloop;
				}
				diff = Math.abs(eval - target);
				if (diff < mDiff) {
					mx = x;
					my = y;
					mDiff = diff;
					System.out.println(x + "," + y + "\t" + eval);
				}
			}
		}
		
		return mx * my;
	}
}
